// Copyright (c) 2006, Inc.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//
// Author: arvin.chen
//
//

#ifndef ALGORITHM_SORT_MERGERECURSION_H_
#define ALGORITHM_SORT_MERGERECURSION_H_

#ifndef ALGORITHM_SORT_BASE_H_
#include "algorithm/sort/base.h"
#endif

namespace algorithm {
	namespace sort {
		
		template<typename T>
		class MergeRecursion : public Base<T> {
		public:

			/**
			* Construction
			*
			* @param
			* @return
			*/
			MergeRecursion() :
				Base<T>::Base(kMergeRecursion)
			{
				
			}

			/**
			* Destruction
			*
			* @param VOID
			* @return
			*/
			~MergeRecursion()
			{

			}

			/**
			* sort
			*
			* @param T arr[]
			* @param int len
			* @return T
			*/
			virtual T* sort(T arr[], int len)
			{
				if (nullptr == arr || 1 >= len) return arr;
				SortRecursion(arr, 0, len - 1);
				return arr;
			}

		protected:
			/**
			* Assignment
			*
			* @param const MergeRecursion& cbase
			* @return MergeRecursion&
			*/
			MergeRecursion& operator=(const MergeRecursion& cbase);

			/**
			* Copy Construction
			*
			* @param const MergeRecursion& cbase
			* @return
			*/
			MergeRecursion(const MergeRecursion& cbase);

		private:

			/**
			* SortRecursion
			*
			* @param T arr[]
			* @param int left
			* @param int right
			* @return void
			*/
			T* SortRecursion(T arr[], int left, int right) {
				// If left == right, it means that the array has only one element, so recursive sorting is not required
				if (left < right) {
					// Separate the large array into two arrays
					int mid = (left + right) / 2;
					// sort the left half
					SortRecursion(arr, left, mid);
					// sort the right half
					SortRecursion(arr, mid + 1, right);
					//Merge array
					MergeArr(arr, left, mid, right);
				}
				return arr;
			}

			/**
			* MergeArr
			* Combine function to combine two ordered arrays
			* arr[left..mif] means an array, arr[mid+1 .. right] means an array
			*
			* @param T arr[]
			* @param int h
			* @param int i
			* @return T*
			*/
			T* MergeArr(T arr[], int left, int mid, int right) {
				//First use a temporary array to merge them together
				//std::vector<T> a(right - left + 1);
				T* a = new T[right - left + 1];
				memset(a, 0x00, sizeof(T) * (right - left + 1));
				int i = left;
				int j = mid + 1;
				int k = 0;
				while (i <= mid && j <= right) {
					if (arr[i] < arr[j]) {
						a[k++] = arr[i++];
					}
					else {
						a[k++] = arr[j++];
					}
				}
				while (i <= mid) a[k++] = arr[i++];
				while (j <= right) a[k++] = arr[j++];
				// Copy the temporary array to the original array
				for (i = 0; i < k; i++) {
					arr[left++] = a[i];
				}
				delete[] a;
				a = nullptr;
				return arr;
			}

		public:
		protected:
		private:

		};
	} // namespace algorithm 
} // namespace sort


#endif  // ALGORITHM_SORT_MERGERECURSION_H_
